/*
Date:20210610 10:42AM
key:经典完全背包问题，如果是一维会有重复。
    因此是dp[i][j]考虑前i个数字凑成金额j的方案个数，全部初始化成0，然后当前int c=k-g*coins[i-1];g从0+1至c<0
*/
class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        int**dp=new int*[coins.size()+1];
        for(int i=0;i<coins.size()+1;i++)
        {
            dp[i]=new int[amount+1];
        }
        //dp[i][j]考虑前i个数字凑成金额j的方案个数
        for(int i=0;i<coins.size()+1;i++)
        {
            for(int k=0;k<amount+1;k++)
            {
                dp[i][k]=0;
            }
        }
        dp[0][0]=1;

        for(int i=1;i<coins.size()+1;i++)
        {
            for(int k=0;k<amount+1;k++)
            {
                //不选的方案一定被加上
                
                //选的方案
                int g=0;
                while(1)
                {
                    int c=k-g*coins[i-1];
                    if(c<0){break;}
                    dp[i][k]+=dp[i-1][c];
                    g++;
                }
            }
        }
        return dp[coins.size()][amount];
    }
};